package week02

// 538. 把二叉搜索树转换为累加树
// https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

// 解1、求前序+中序，中序求后缀和，构造累加树
// 解2、逆中序遍历求和（后、中、左）

func convertBST(root *TreeNode) *TreeNode {
	//preList := pre(root, []int{})
	//midList := mid(root, []int{})
	//sumList := make([]int, len(midList))
	//copy(sumList, midList)
	//// 求后缀和
	//for i := len(sumList)-2; i >= 0; i-- {
	//	sumList[i] = sumList[i] + sumList[i+1]
	//}
	//return genTree(preList, midList, sumList)

	convertBST2(root, 0)
	return root
}

// 构造累加树
func genTree(preList, midList, sumList []int) *TreeNode {
	if len(preList) == 0 {
		return nil
	}
	// 找到根节点在中序的位置
	var rootIndex int
	for i := 0; i < len(midList); i++ {
		if preList[0] == midList[i] {
			rootIndex = i
			break
		}
	}

	root := &TreeNode{
		Val: sumList[rootIndex],
	}
	root.Left = genTree(preList[1:rootIndex+1], midList[:rootIndex], sumList[:rootIndex])
	root.Right = genTree(preList[rootIndex+1:], midList[rootIndex+1:], sumList[rootIndex+1:])
	return root
}

// 前序遍历
func pre(root *TreeNode, ans []int) []int {
	if root == nil {
		return ans
	}
	ans = append(ans, root.Val)
	ans = pre(root.Left, ans)
	ans = pre(root.Right, ans)
	return ans
}

// 中序遍历
func mid(root *TreeNode, ans []int) []int {
	if root == nil {
		return ans
	}
	ans = mid(root.Left, ans)
	ans = append(ans, root.Val)
	ans = mid(root.Right, ans)
	return ans
}

// 逆中序遍历求和
func convertBST2(root *TreeNode, sum int) int {
	if root == nil {
		return sum
	}
	sum = root.Val + convertBST2(root.Right, sum)
	root.Val = sum
	sum = convertBST2(root.Left, sum)
	return sum
}

type TreeNode struct {
	Val int
	Left, Right *TreeNode
}